﻿#define MirrorRouteTable
#define SortLastTrainsRoutes
//#define TESTING_BitsNotTouched
//#define TryParallel

using System;
using System.Collections.Generic;
using System.Diagnostics;
using TrainGame.Model;
using TrainGame.Common;

namespace TrainGame.Engine.RouteCalc
{
	/// <summary>
	/// Route Calculator functions.  Entry points are all static
	/// </summary>
	static public class RouteCalculator
	{
		/// <summary>
		/// Finds best routes on the REAL GAMEBOARD, Game.Gameboard
		/// </summary>
		/// <param name="company"></param>
		/// <param name="Trains"></param>
		/// <returns></returns>
		static public RouteCollection FindBestRoutes(PublicCompany company, TrainCollection Trains)
		{
			return FindBestRoutes(company.Game.Gameboard, company, Trains, true);
		}

		/// <summary>
		/// Finds best routes on the passed-in Gameboard, which can be different from the real in-play gameboard
		/// </summary>
		/// <param name="gameboard"></param>
		/// <param name="company"></param>
		/// <param name="Trains"></param>
		/// <param name="allowTracing">allows caller to disable trace output during FindBestRoutes</param>
		/// <returns></returns>
		static public RouteCollection FindBestRoutes(Gameboard gameboard, PublicCompany company, TrainCollection Trains, bool allowTracing)
		{
			XTrace.Push(allowTracing);
			try
			{
				/*
				 * best route collection = new empty route collection
				 * if no trains, return empty route collection
				 *
				 * build routes for each train size
				 * for each route in each train size
				 *     build hastable of all conflicting routes in all other train route collections
				 *
				 * select first train
				 * for each route
				 *     create a test route collection
				 *     apply this route to first train
				 *     add route to test collection
				 */
				Stopwatch watch = new Stopwatch();
				watch.Start();
				RouteCollection BestRoutes = new RouteCollection();

				if (Trains.Count == 0)
					goto done;

				City[] AllCities = City.GetAllCities(gameboard, company);

				//
				//  Build routes for each train size
				//
				Dictionary<int, RouteCollection> TrainSizeRoutes = new Dictionary<int, RouteCollection>();
				foreach (Train train in Trains)
				{
					int key = train.Stops;
					if (!TrainSizeRoutes.ContainsKey(key))
					{
						RouteCollection routeCollection = BuildRoutes(gameboard, company, AllCities, true, !train.UnlimitedStops, train.Stops, new List<string>());
						TrainSizeRoutes.Add(key, routeCollection);
						XTrace.Trace(" >> {0} train: {1} routes", train.Name, routeCollection.Count);
					}
				}

				TimeSpan first = watch.Elapsed;
				XTrace.Trace(" >> time building all routes: {0}", first.ToString());

				//
				//	Sort the trains longest-first - needed for proper route collision handling
				//
				TrainCollection OrderedTrains = new TrainCollection(Trains);
				OrderedTrains.SortHighestToLowest();

				//
				//  Sort the routes highest-value-first - to optimize the combinatorial loops in BuildTestRoutesInlined.
				//  Only needed for the smallest train's routes, since that will be the inner-most loop. And only needed
				//  if at least two trains!
				//
				if (OrderedTrains.Count > 1)
				{
					int key = OrderedTrains[OrderedTrains.Count - 1].Stops;
					TimeSpan before = watch.Elapsed;
					TrainSizeRoutes[key].SortHighestToLowest();
					TimeSpan delta = watch.Elapsed.Subtract(before);
					XTrace.Trace(" >> time sorting {0}-train routes: {1}", key, delta.ToString());
				}

				//
				//  Configure the comparison algorithm
				//
				RouteCalcConfig config = new RouteCalcConfig();
				config.UseInlinedAlgorithm = true;
#if StillTesting
			// The inlined algorithm uses more memory but runs faster than the recursive algorithm.
			// We start getting into memory trouble when there are two diesels and a smaller train in CGR.
			//
			// The inlined algorithm allocates NxN route combinations for the first two trains, then applies the smaller train's
			// routes against those combinations.  With D/D/6 and ~900,000 D routes on a complex end-game map, this is where
			// the 900k x 900k combinations blows out memory.  This ONLY happens when we have three trains, because the
			// memory is allocated for the first N-1 trains in combination.  I.e. if CGR has only two D's, we'll allocate
			// 900,000 'combinations', which is not a problem.  With two D's and a 6, we allocate 900,000 x 900,000 =
			// 810,000,000,000 combinations (810 billion!).  You can see where that would tend to blow out memory :-)
			//
			// So for that situation, we'll go back to the recursive algorithm, trading back the memory usage for the extra cpu time.
			// Note: So far, this hasn't been necessary for say three 8's in CGR, only for diesels.
			if ((OrderedTrains.Count > 2) &&		// 3 or more trains
			  (OrderedTrains[0].Stops == 0) &&		// first is a diesel (relies on being sorted longest to shortest)
			  (OrderedTrains[1].Stops == 0))		// second is a diesel
//			if (OrderedTrains.Count > 2)		// 3 or more trains
				config.UseInlinedAlgorithm = false;

			// Hmm, turns out that 2 D's using inlined algortihm takes way too long...

			// Also turns out that 2 8's and a 6 on a complex map also blows out memory
#endif // StillTesting

				if (config.UseInlinedAlgorithm)
					XTrace.Trace(" >> choosing bit-vector ANDing algorithm INLINED");
				else
					XTrace.Trace(" >> choosing bit-vector ANDing algorithm RECURSIVE");

				//
				//	Build a map of all conflicting routes; each route gets a list of all other routes that conflict with it
				//	(across all train sizes)
				//
				config.bitArraySize = 0;
				config.bitArraySize = BuildRouteBitArrays(TrainSizeRoutes);	// computes the critical bit-array route-ids we use for collision detection
				config.ulongsInBitArray = (config.bitArraySize + 63) / 64;

#if TESTING_BitsNotTouched
			//
			//  Build lookup table to streamline the overlap-detection phase.
			//
			List<Route[]> tableOfRouteCollections = BuildTableOfRouteCollections(TrainSizeRoutes, config.bitArraySize);
#endif // TESTING_BitsNotTouched

				//
				//	Build test route collections and see which is best
				//
				if (config.UseInlinedAlgorithm)
				{
					// this version unrolls and inlines the recursion
					BestRoutes = BuildTestRoutesInlined(OrderedTrains, TrainSizeRoutes,
#if TESTING_BitsNotTouched
					tableOfRouteCollections,
#endif // TESTING_BitsNotTouched
 config);
				}
				else
				{
					// TODO: If SortLastTrainsRoutes works out, we won't need the recursive algorithm at all - obsolete it
					// recursive method
					BestRoutes = BuildTestRoutesRecursively(OrderedTrains, TrainSizeRoutes, config);
				}

			done:
				watch.Stop();
				XTrace.Trace(" >> FindBestRoutes duration {0}", watch.Elapsed.ToString());
				return (BestRoutes);
			}
			finally
			{
				XTrace.Pop();
			}
		}

#if TESTING_BitsNotTouched
		/// <summary>
		///  Build lookup table to streamline the overlap-detection phase (which is the most time-consuming
		///  phase when a company has many long trains - especially CGR with 8's or D's).  The key goal is to avoid
		///  iterating over conflicting routes entirely, rather than test their bit arrays to reject them.
		///  Instead of one big collection of all routes, we'll build N smaller collections, where N is the number of
		///  unique hexsides (bits in the bit array), and the contents of each collection is all the routes that use that
		///	 hexside.  That way we can build valid route combinations without actually comparing bit arrays.
		/// </summary>
		/// <remarks>
		/// PROBLEM: This approach puts the same route in multiple collections, with the result that the same route
		/// gets compared and even added multiple times during BuildTestRoutes.  Too much memory used, and all those
		/// extra comparisons eats up the efficiencies we get from rejecting colliding routes.
		/// </remarks>
		/// <param name="TrainSizeRoutes"></param>
		/// <param name="BitArraySize"></param>
		/// <returns>array of route Lists, one list per bit, i.e. config.bitArraySize</returns>
		static private List<Route[]> BuildTableOfRouteCollections(Dictionary<int, RouteCollection> TrainSizeRoutes, int BitArraySize)
		{
			// build a table of route collections first so we can add to them
			List<RouteCollection> routeCollections = new List<RouteCollection>();
			for (int i = 0; i < BitArraySize; i++)
				routeCollections.Add(new RouteCollection());

			// now fill them
			// we don't care about which train size each route needs, we just map each route via its bit array
			foreach (RouteCollection collection in TrainSizeRoutes.Values)
			{
				foreach (Route route in collection)
				{
					route.CachedStops = route.Stops;

					ushort[] BitsTouched = GetBitsTouched(route, BitArraySize);
					foreach (int bit in BitsTouched)
						routeCollections[bit].Add(route);
				}
			}

			// convert to route arrays because they're faster to iterate than RouteCollections
			List<Route[]> routeTable = new List<Route[]>();
			foreach (RouteCollection collection in routeCollections)
				routeTable.Add(collection.GetAsArray());

			return routeTable;
		}

		static private ushort[] GetBitsTouched(Route route, int BitArraySize)
		{
			return GetBitsTouched(route.TrackSegmentBitArray, BitArraySize, true);
		}

		static private ushort[] GetBitsNotTouched(ulong[] TrackSegmentBitArray, int BitArraySize)
		{
			return GetBitsTouched(TrackSegmentBitArray, BitArraySize, false);
		}

		static private ushort[] GetBitsTouched(ulong[] TrackSegmentBitArray, int BitArraySize, bool WantTouched)
		{
			List<ushort> bits = new List<ushort>();
			int word = 0;
			ulong mask = 1;

			for (ushort bit = 0; bit < BitArraySize; )
			{
				if ((WantTouched && ((TrackSegmentBitArray[word] & mask) != 0)) ||
				  ((! WantTouched) && ((TrackSegmentBitArray[word] & mask) == 0)) )
					bits.Add(bit);

				bit++;
				if ((bit & 63) < 63)
					mask <<= 1;
				else
				{
					mask = 1;
					word++;
				}
			}

			return bits.ToArray();
		}
#endif // TESTING_BitsNotTouched

		static public RouteCollection BuildRoutes(Gameboard gameboard, PublicCompany company, City[] StartCities, bool MustContainToken, bool LimitStops, int stops, List<string> hexVisits)
		{
#if MirrorRouteTable
			// a lookup table for forward and reverse route ids, so we can avoid adding mirror routes
			Dictionary<string, Route> routeLookup = new Dictionary<string, Route>();
#endif // MirrorRouteTable
			RouteCollection Routes = new RouteCollection();

			foreach (City city in StartCities)
			{
				RouteCollection newRoutes = BuildRoutesFromCity(gameboard, city, company, LimitStops, stops, hexVisits);

				//Routes.AddRoutes(newRoutes);

				// instead of just adding them and having to RemoveMirrorRoutes later, check for mirrors now
				foreach (Route route in newRoutes)
				{
#if MirrorRouteTable
					// TODO: could probably just check the route bit arrays directly - exact equal means discard
					// BUT! bit array's can't be computed yet because we don't have all the track segments yet

					string forward = route.GetRouteID();
					string reverse = route.GetReverseRouteID();

					bool AddIt = (!routeLookup.ContainsKey(forward)) && (!routeLookup.ContainsKey(reverse));
					//bool AddIt = ! IsRouteInCollection_BitArrayComparison(route, Routes);

					// add route only if its id isn't already in the table
					if (AddIt)
					{
						routeLookup[forward] = route;
						routeLookup[reverse] = route;
#endif // MirrorRouteTable
						// cache some values for faster route comparisons
						route.CachedValue = route.Value;
						Routes.Add(route);

						// TODO: instead of just adding to a single list, keep 1 list for each bit in the bitarray,
						//		 and add the route to EACH bit's list for bits in the route
						// NOTE: will have to post-compute that multi lookup table, again because bit arrays aren't possible at this point in the algorithm
#if MirrorRouteTable
					}
#endif // MirrorRouteTable
				}
			}

			return (Routes);
		}

		static private bool IsRouteInCollection_BitArrayComparison(Route route, RouteCollection routes)
		{
			foreach (Route r in routes)
			{
				bool match = true;
				for (int i = 0; i < route.TrackSegmentBitArray.Length; i++)
				{
					if (route.TrackSegmentBitArray[i] != r.TrackSegmentBitArray[i])
					{
						match = false;
						break;
					}
				}
				if (match)
					return true;
			}
			return false;
		}

		static private RouteCollection BuildRoutesFromCity(Gameboard gameboard, City city, PublicCompany company, bool LimitStops, int stops, List<string> hexVisits)
		{
			if (!hexVisits.Contains(city.Hex.Location))
				hexVisits.Add(city.Hex.Location);

			RouteCollection Routes = new RouteCollection();
			foreach (TrackSegment track in city.Hex.TrackSegments)
			{
				SegmentEndpoint startEndpoint;
				SegmentEndpoint endEndpoint;
				//
				//  Only consider tracks segments that start or end at a city
				//
				if (track.StartsAtCity(city, out startEndpoint, out endEndpoint))
				{
					//
					//  create a starting route with this track segement
					//
					TrackSegment newSegment = new TrackSegment(city.Hex, startEndpoint, endEndpoint);
					Route baseRoute = new Route();
					baseRoute.AddTrackSegment(newSegment);

					//
					//  recursively follow paths along this route (can add additional routes to the collection)
					//
					BuildDownstreamRoutes(gameboard, company, Routes, baseRoute, LimitStops, stops - 1, hexVisits);
				}
			}

			return (Routes);
		}

		static private void BuildDownstreamRoutes(Gameboard gameboard, PublicCompany company, RouteCollection Routes, Route baseRoute, bool LimitStops, int stops, List<string> hexVisits)
		{
			int count = baseRoute.TrackSegments.Length;
			TrackSegment lastTrack = baseRoute.TrackSegments[count - 1];
			SegmentEndpoint startEndpoint;
			SegmentEndpoint endEndpoint;
			if (lastTrack.End.AtCity)
			{
				stops--;
				//
				//  See if we've hit the train size limit, or route is blocked by tokens
				//
				if ((LimitStops && (stops <= 0)) ||
					(!CanRunThrough(lastTrack.End.City, company)))
				{
					if (baseRoute.ContainsToken(company))
						Routes.Add(baseRoute);
					// else discard the route by not adding it
					return;
				}

				//
				//  Examine all tracks out of this city.  Discard those that already exist in the route.
				//
				foreach (TrackSegment track in lastTrack.End.City.Hex.TrackSegments)
				{
					if (track.StartsAtCity(lastTrack.End.City, out startEndpoint, out endEndpoint) &&
						(!baseRoute.ConflictsWith(track)))
					{
						// abort this track segment if hits an existing city in this route
						if (/*track.End*/endEndpoint.AtCity && baseRoute.ContainsCity(/*track.End*/endEndpoint.City))
							continue;
						//
						//  make a copy of the route, add the segment to it, and finish those routes
						//
						Route newRoute = new Route(baseRoute);
						TrackSegment newSegment = new TrackSegment(lastTrack.Hex, startEndpoint, endEndpoint);
						newRoute.AddTrackSegment(newSegment);
						BuildDownstreamRoutes(gameboard, company, Routes, newRoute, LimitStops, stops, hexVisits);
					}
				}
			}
			else
			{
				//
				//  Find destination hex; run all incoming segments on this hexside
				//
				string sNextHex = (string)lastTrack.Hex.Neighbors[lastTrack.End.Hexside];
				if (sNextHex != null)
				{
					string hexside = PublicCompany.InverseDirection(lastTrack.End.Hexside);

					GameboardHex destHex = gameboard.GameboardHexes[sNextHex];
					if (destHex != null)
					{
						bool FoundOne = false;
						foreach (TrackSegment track in destHex.TrackSegments)
						{
							if (track.StartsAtHexside(hexside, out startEndpoint, out endEndpoint) &&
								(!baseRoute.ConflictsWith(track)))
							{
								if (!hexVisits.Contains(sNextHex))
									hexVisits.Add(sNextHex);

								// abort this track segment if hits an existing city in this route
								if (endEndpoint.AtCity && baseRoute.ContainsCity(endEndpoint.City))
									continue;
								//
								//  make a copy of the route, add the segment to it, and finish those routes
								//
								FoundOne = true;
								Route newRoute = new Route(baseRoute);
								TrackSegment newSegment = new TrackSegment(destHex, startEndpoint, endEndpoint);
								newRoute.AddTrackSegment(newSegment);
								BuildDownstreamRoutes(gameboard, company, Routes, newRoute, LimitStops, stops, hexVisits);
							}
						}
						//
						//  hit end of track before full number of stops
						//
						if ((!FoundOne) && (baseRoute.Stops >= 2))
						{
							baseRoute.TruncateToCity();
							if (baseRoute.ContainsToken(company))
								Routes.Add(baseRoute);
						}
					}
				}
			}
		}

		static private RouteCollection BuildTestRoutesRecursively(TrainCollection Trains, Dictionary<int, RouteCollection> TrainSizeRoutes, RouteCalcConfig config)
		{
			long count = 0;
			_callstoBuildTestRoutesRecursively = 0;
			RouteCollection BestRoutes = new RouteCollection();

			Train BaseTrain = Trains[0];
			RouteCollection BaseRoutes = TrainSizeRoutes[BaseTrain.Stops];
			foreach (Route BaseRoute in BaseRoutes)
			{
				RouteCollection TestRoutes = new RouteCollection();
				TestRoutes.Add(BaseRoute);
				TestRoutes.CachedTotalValue = BaseRoute.CachedValue;

				if (Trains.Count > 1)
					BuildTestRoutesRecursively(ref TestRoutes, Trains, 1, TrainSizeRoutes, config);

				if (TestRoutes.CachedTotalValue > BestRoutes.CachedTotalValue)
					BestRoutes = TestRoutes;
				count++;
			}
			XTrace.Trace(" >> {0} total route collections evaluated (at top level)", count);
			//
			// JoeB: calls to BuildTestRoutesRecursively is a critical performance indicator, and it
			// jumps geometrically with each additional train a railroad has.
			//		1 train, 0 calls
			//		2 trains, N calls, where N is the number of routes in the 2nd train's collection
			//		3 trains, N x M calls, where M is the number of routes in the 3rd trains collection
			XTrace.Trace(" >> {0} total calls to BuildTestRoutesRecursively", _callstoBuildTestRoutesRecursively);
			return (BestRoutes);
		}

		static private long _callstoBuildTestRoutesRecursively;
		static private void BuildTestRoutesRecursively(ref RouteCollection TestRoutes, TrainCollection Trains, int FirstTrain, Dictionary<int, RouteCollection> TrainSizeRoutes, RouteCalcConfig config)
		{
			_callstoBuildTestRoutesRecursively++;
			// Save a copy of the original route collection (we WILL be modifying TestRoutes)
			RouteCollection origRoutes = new RouteCollection(TestRoutes);
			origRoutes.CachedTotalValue = TestRoutes.CachedTotalValue;

			Train thisTrain = Trains[FirstTrain];
			RouteCollection thisRoutes = (RouteCollection)TrainSizeRoutes[thisTrain.Stops];
			bool AddThisRoute;

			foreach (Route route in thisRoutes)
			{
				// Do we add this route?
				AddThisRoute = !BitVectorConflictsWith(route, origRoutes, config.bitArraySize);

				if (AddThisRoute)
				{
					RouteCollection bestRoutes = new RouteCollection(origRoutes);	// make a copy
					bestRoutes.Add(route);
					bestRoutes.CachedTotalValue = origRoutes.CachedTotalValue + route.CachedValue;

					if (FirstTrain + 1 < Trains.Count)
						BuildTestRoutesRecursively(ref bestRoutes, Trains, FirstTrain + 1, TrainSizeRoutes, config);

					if (bestRoutes.CachedTotalValue > TestRoutes.CachedTotalValue)
						TestRoutes = bestRoutes;
				}
			}
		}

		static private RouteCollection BuildTestRoutesInlined(TrainCollection Trains,
			Dictionary<int, RouteCollection> TrainSizeRoutes,
#if TESTING_BitsNotTouched
			List<Route[]> tableOfRouteCollections,
#endif // TESTING_BitsNotTouched
			RouteCalcConfig config)
		{
			ulong nEval = 0;
			ulong nValid = 0;
			ulong nAdded = 0;
			ulong nBetter = 0;

			Stopwatch watch = new Stopwatch();
			watch.Start();

			List<RouteCollection> RouteCombinations = new List<RouteCollection>();
			RouteCollection dummy = new RouteCollection();
			dummy.CachedTotalValue = 0;
			dummy.ORedRouteBitArray = new ulong[config.ulongsInBitArray];

			RouteCombinations.Add(dummy);
			RouteCollection BestRoutes = dummy;

			try // this try/catch is to protect against out-of-memory exceptions
			{
				for (int train = 0; train < Trains.Count; train++)
				{
					bool OnLastTrain = (train == Trains.Count - 1);
					Train ThisTrain = Trains[train];
					// accessing as a simple array gives better perf (demonstrated via profiling)
					//RouteCollection ThisTrainRoutes = TrainSizeRoutes[ThisTrain.Stops];
					Route[] ThisTrainRoutes = TrainSizeRoutes[ThisTrain.Stops].GetAsArray();

					// try combining this train's route collections with the saved valid combinations from previous trains
					int lastValidCombination = RouteCombinations.Count;	// needed because we'll be adding more

					// TODO: try parallelizing this loop. So far, parallel is taking twice as long, and can't avoid the lock
#if TryParallel
					int DesiredNumberOfParallelThreads = Environment.ProcessorCount; // or some small multiple of core count?
					int ChunkSize = lastValidCombination / DesiredNumberOfParallelThreads;
					Parallel.For(0, DesiredNumberOfParallelThreads, delegate(int chunk)
					{
						int chunkStart = chunk * ChunkSize;
						int chunkEnd = Math.Max(lastValidCombination, chunkStart + ChunkSize);	// last chunk picks up any remainder

						// used to accumulate route combinations while avoiding locking the destination list on each add
						List<RouteCollection> MyNewRoutes = new List<RouteCollection>();
						RouteCollection MyBestRoutes = new RouteCollection();
						MyBestRoutes.CachedTotalValue = BestRoutes.CachedTotalValue;	// start with a dummy route with the actual best value

						for (int valid = chunkStart; valid < chunkEnd; valid++)
#else
						for (int valid = 0; valid < lastValidCombination; valid++)
#endif // TryParallel
						{
#if TryParallel
#endif // TryParallel
							RouteCollection validCombination = RouteCombinations[valid];
							// This loop is substantially faster with a Route[] vs. the default List<Route>
							// And with the array the loop is a tiny bit faster with for(r=) instead of foreach()  (though for is slower with a List<>)
							//foreach (Route route in ThisTrainRoutes)
#if TESTING_BitsNotTouched
						ushort[] BitsNotTouched = GetBitsNotTouched(validCombination.ORedRouteBitArray, config.bitArraySize);
						for (int index=0; index < BitsNotTouched.Length; index++)
						{
							int whichBit = BitsNotTouched[index];
							for (int r = tableOfRouteCollections[whichBit].Length - 1; r >= 0; r--)
							{
								Route route = tableOfRouteCollections[whichBit][r];
								// the table has all routes together, so reject too-long routes
								if ((ThisTrain.Stops > 0) && (ThisTrain.Stops < route.CachedStops))
									goto endofloop;
#else
							for (int r = 0; r < ThisTrainRoutes.Length; r++)
							//for (int r = ThisTrainRoutes.Length - 1; r >= 0; r--)
							{
								Route route = ThisTrainRoutes[r];
#endif
								nEval++;

#if ! TESTING_BitsNotTouched
								//AddThisRoute = !BitVectorConflictsWith(route, validCombination, config.bitArraySize);
								// try it inlined
								// examine the collection's combined route segment bits
								//if (AndBits(validCombination.ORedRouteBitArray, route.TrackSegmentBitArray))
								//	AddThisRoute = false;
								// inline the AndBits
								for (int i = 0; i < config.ulongsInBitArray; i++)
								//for (int i = 0; i < validCombination.ORedRouteBitArray.Length; i++)
								{
									if ((validCombination.ORedRouteBitArray[i] & route.TrackSegmentBitArray[i]) != 0)
										goto nextIteration;	// we really want a break+continue the outer loop; this is a tiny bit faster than testing the AddThisRoute flag
								}
#endif // ! TESTING_BitsNotTouched

								nValid++;

								// Special - If we're on the last train, we don't need to add this new combination
								// to the route collection list.  But we still need to save it if it's the best
								// route collection so far.
								bool BetterCombination =
									(validCombination.CachedTotalValue + route.CachedValue > BestRoutes.CachedTotalValue);

								if (BetterCombination || (!OnLastTrain))
								{
									RouteCollection newCombination = new RouteCollection(validCombination);	// make a copy
									newCombination.ORedRouteBitArray = new ulong[validCombination.ORedRouteBitArray.Length];
									for (int i = 0; i < validCombination.ORedRouteBitArray.Length; i++)
										newCombination.ORedRouteBitArray[i] = validCombination.ORedRouteBitArray[i];
									newCombination.Add(route);
									newCombination.CachedTotalValue = validCombination.CachedTotalValue + route.CachedValue;
									// produce a Collection specific bit mask
									OrBits(ref newCombination.ORedRouteBitArray, route.TrackSegmentBitArray);
									// TESTING: cache the list of bits not in the route
									// - consumes a lot of memory, might be better to just compute as needed
									//newCombination.BitsNotTouched = GetBitsNotTouched(newCombination.ORedRouteBitArray, config.bitArraySize);

									if (BetterCombination)
									{
#if TryParallel
										MyBestRoutes = newCombination;
#else
										nBetter++;
										BestRoutes = newCombination;
#endif // TryParallel
									}
									if (!OnLastTrain)
									{
#if TryParallel
										MyNewRoutes.Add(newCombination);
#else
										nAdded++;
										RouteCombinations.Add(newCombination);
#endif // TryParallel
									}
								}
								// Since routes are sorted highest to lowest value, when we're looking at the
								// last train we can be certain that THIS is the best route we'll find, so we're done!
								// (It might not have resulted in a better combination, which is why this is outside the
								// BetterCombination test. This might be a junky combo of earlier trains' routes plus a
								// decent last-train route.)
								if (OnLastTrain && (Trains.Count > 1))
									goto exitInnerLoop;	// all done!

							// we use this label as hopefully the quickest way to 'goto' around the adding
							nextIteration:
								continue;	// compiler requires a statement here; this is an attempt to make it innocuous (hopefully optimized away)
							}
#if SortLastTrainsRoutes
						exitInnerLoop:
							continue;	// compiler requires a statement here too
#endif // SortLastTrainsRoutes
#if TESTING_BitsNotTouched
						}
						BitsNotTouched = null;
#endif
#if TryParallel
						}
						// The for loop is done, now add all combinations to the base list
						if (MyNewRoutes.Count > 0)
						{
							// Support parallel threads adding to the collection
							// The lock also controls access to BestRoutes, nBetter, and nAdded
							lock (RouteCombinations)
							{
								foreach (RouteCollection newCombination in MyNewRoutes)
								{
									RouteCombinations.Add(newCombination);
									nAdded++;
								}
								if (MyBestRoutes.CachedTotalValue > BestRoutes.CachedTotalValue)
								{
									BestRoutes = MyBestRoutes;
									nBetter++;
								}
							}
						}
					});	// trailing ); is needed to close out the Parallel.For delegate from above
#else
					}
#endif // TryParallel
				}
			}
			catch (OutOfMemoryException oom)
			{
				// yeah, this does happen with many long trains on a complex map (e.g. D/D/6 CGR in late game)
				// so lets try to recover enough so that the app can continue

				RouteCombinations = null;	// this is where all the memory is used; free it to give some headroom

				XTrace.Trace("** Exception: {0}\n{1}", oom.Message, oom.ToString());
			}

			watch.Stop();
			XTrace.Trace(" >> BuildTestRoutesInlined ran for " + watch.Elapsed.ToString());
			XTrace.Trace(" >> total route collections evaluated: " + nEval);
			XTrace.Trace(" >> valid route combinations found: " + nValid);
			XTrace.Trace(" >> 'better' route combinations found: " + nBetter);
			XTrace.Trace(" >> route combinations added to collection: " + nAdded);

			return (BestRoutes);
		}

		static private int BuildRouteBitArrays(Dictionary<int, RouteCollection> TrainSizeRoutes)
		{
			Dictionary<string, int> TrackSegmentHash = new Dictionary<string, int>();
			int hexSideId = 0;
			Stopwatch watch = new Stopwatch();
			watch.Start();

			// generate the hexside hash table
			foreach (RouteCollection collection in TrainSizeRoutes.Values)
			{
				foreach (Route route in collection)
				{
					foreach (TrackSegment ts in route.TrackSegments)
					{
						if (!ts.Start.AtCity)
							AddHexsideHash(TrackSegmentHash, ts.Hex, ts.Start, ref hexSideId);
						if (!ts.End.AtCity)
							AddHexsideHash(TrackSegmentHash, ts.Hex, ts.End, ref hexSideId);
					}
				}
			}
			// build each route's bit vector (with one bit for each unique hexside)
			int numInts = (hexSideId + 63) / 64;
			foreach (RouteCollection collection in TrainSizeRoutes.Values)
			{
				foreach (Route route in collection)
				{
					// create the bit array
					//route.TrackSegmentBitArray = new BitArray(hexSideId/*number of bits*/);
					route.TrackSegmentBitArray = new ulong[numInts];

					// fill it in from the track segments
					foreach (TrackSegment ts in route.TrackSegments)
					{
						if (!ts.Start.AtCity)
							SetBit(ref route.TrackSegmentBitArray, ts.Start.HexsideId);	//route.TrackSegmentBitArray[ts.Start.HexsideId] = true;
						if (!ts.End.AtCity)
							SetBit(ref route.TrackSegmentBitArray, ts.End.HexsideId);	//route.TrackSegmentBitArray[ts.End.HexsideId] = true;
					}
				}
			}

			watch.Stop();
			XTrace.Trace(" >> BuildRouteBitArrays duration {0}, bit vector size = {1}", watch.Elapsed.ToString(), hexSideId);

			return hexSideId;	// number of bits
		}

		static private void AddHexsideHash(Dictionary<string, int> TrackSegmentHash, GameboardHex hex, SegmentEndpoint ep, ref int hexSideId)
		{
			//hash = hex.Location + ep.Hexside;
			string sNextHex = (string)hex.Neighbors[ep.Hexside];
			string hash = hex.Location + sNextHex;

			if (TrackSegmentHash.ContainsKey(hash))
				ep.HexsideId = TrackSegmentHash[hash];
			else
			{
				ep.HexsideId = hexSideId;
				TrackSegmentHash.Add(hash, hexSideId);

				// also need the reverse hex-to-hex hash
				string reversehash = sNextHex + hex.Location;
				TrackSegmentHash.Add(reversehash, hexSideId);

				hexSideId++;
			}
		}

		static private void SetBit(ref int[] array, int bitnum)
		{
			int index = bitnum >> 5;
			bitnum &= 0x1f;
			array[index] |= 1 << bitnum;
		}
		static private void SetBit(ref ulong[] array, int bitnum)
		{
			int index = bitnum >> 6;
			bitnum &= 0x3f;
			array[index] |= ((ulong)1) << bitnum;
		}
		static private void SetBit(ref ulong bits, int bitnum)
		{
			int index = bitnum >> 6;
			bitnum &= 0x3f;
			bits |= ((ulong)1) << bitnum;
		}

		// return true if result is non-zero
		static private bool AndBits(ref int[] array1, int[] array2)
		{
			// assumes arrays are same size
			for (int i = 0; i < array1.Length; i++)
			{
				if ((array1[i] & array2[i]) != 0)
					return true;
			}
			return false;
		}
		static private bool AndBits(ref ulong[] array1, ulong[] array2)
		{
			// assumes arrays are same size
			for (int i = 0; i < array1.Length; i++)
			{
				if ((array1[i] & array2[i]) != 0)
					return true;
			}
			return false;
		}
		static private bool AndBits(ref ulong bits1, ulong bits2)
		{
			return ((bits1 & bits2) != 0);
		}

		// OR the bits into array1 (modifies array1)
		static private void OrBits(ref int[] array1, int[] array2)
		{
			// assumes arrays are same size
			for (int i = 0; i < array1.Length; i++)
				array1[i] |= array2[i];
		}
		static private void OrBits(ref ulong[] array1, ulong[] array2)
		{
			// assumes arrays are same size
			for (int i = 0; i < array1.Length; i++)
				array1[i] |= array2[i];
		}
		static private void OrBits(ref ulong bits1, ulong bits2)
		{
			bits1 |= bits2;
		}

		static private bool BitVectorConflictsWith(Route route, RouteCollection collection, int bitArraySize)
		{
			//int numints = (bitArraySize + 31) / 32;
			//int[] results = new int[numints];

			foreach (Route test in collection)
			{
				// there's no easy way to test every bit in Anded, so copy to an int array we CAN test
				//BitArray Anded = route.TrackSegmentBitArray.And(test.TrackSegmentBitArray);
				//Anded.CopyTo(results,0);
				//foreach (int i in results)
				//    if (i != 0)
				//        return true;

				if (AndBits(ref route.TrackSegmentBitArray, test.TrackSegmentBitArray))
					return true;
			}
			return false;
		}

		/// <summary>
		/// Return true if the city is not tokened up, or the company has a token here
		/// </summary>
		/// <param name="city"></param>
		/// <param name="company"></param>
		/// <returns></returns>
		static private bool CanRunThrough(City city, PublicCompany company)
		{
			if (city.Offboard)
				return false;

			if (company == null)
				return true;	// we're not checking for a specific company, just for track connectivity

			if (city.TokenSpots < 1)	// non-tokenable town never blocks
				return true;

			if (city.Tokens < city.TokenSpots)
				return true;

			foreach (Token token in city.Hex.Tokens)
			{
				// this company's token?
				if (token.Company == company)
				{
					if (!city.Hex.SeperateCities)
						return true;
					// if a multi-city tile, make sure token in this city
					if (city.HexsidesConnectsTo.Contains(token.LocationInHex.Compass))
						return true;
				}
			}
			return false;
		}
	}

	/// <summary>
	/// describes HOW to calculate best routes (which algorithm and associated info)
	/// </summary>
	public class RouteCalcConfig
	{
		/// <summary>
		/// Number of bits in the bit array
		/// </summary>
		public int bitArraySize;	// requires all route.TrackSegmentBitArray's to be created

		/// <summary>
		/// Number of ulongs it takes to hold bitArraySize bits
		/// </summary>
		public int ulongsInBitArray;

		/// <summary>
		/// Use inlined algorithm?  If false, use recursive algorithm
		/// </summary>
		public bool UseInlinedAlgorithm = true;
	}
}
